\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath}
%\usepackage{mlapa}

\newcommand{\eat}[1]{}

\title{User Manual for Libra 0.4.0}
\author{Daniel Lowd $<$lowd@cs.uoregon.edu$>$}
\begin{document}
\maketitle

\section{Introduction}

A number of graphical model toolkits have been developed over the
years, quite a few of which are open source.  Libra is the first open
source machine learning toolkit to directly support Bayesian networks
(BNs) with decision tree conditional probability distributions (CPDs),
Markov networks (MNs) with sparse factors, and arithmetic circuits
(ACs) as an inference representation.\footnote{The WinMine
Toolkit~\cite{WinMine} and Ace (http://reasoning.cs.ucla.edu/ace/)
were partial inspirations for Libra and offer some overlapping
functionality, but neither is open source.} Libra stands for
\emph{L}earning and \emph{I}nference in \emph{B}ayesian networks,
\emph{R}andom fields and \emph{A}rithmetic circuits.  In version
0.4.0, Libra also supports dependency networks.  Libra's strength
is exploiting context-specific independence to allow exact inference
in models with high treewidth.  The latest version of Libra can be
obtained from {\tt http://libra.cs.uoregon.edu/}.  Libra is released
under a modified BSD license.

This user manual gives a brief overview of Libra's functionality,
describes the file formats used, and explains the operation of each
command in the toolkit.
See the tutorial for a step-by-step introduction to using
Libra, and the developer's guide for information on modifying and
extending Libra.

% TODO -- Add a background section?
%\section{Background}

\section{Algorithms}

Libra includes implementations of various algorithms for learning and
inference with different representations.  Representations include
Bayesian networks (BNs) with tree or table conditional probability
distributions (CPDs); Markov networks (MNs) with factors represented
as trees, tables, or sets of (mutually exclusive) conjunctive
features; and dependency networks (DNs) with tree or table CPDs.

The following inference algorithms are supported for BNs, MNs,
and DNs:
\begin{itemize}
\item Mean field inference ({\tt mf})~\cite{lowd&shamaei11}
\item Gibbs sampling ({\tt gibbs})
\end{itemize}

For BNs and MNs, three more inference algorithms are supported:
\begin{itemize}
\item Belief propagation ({\tt bp})~\cite{murphy&al99}
\item Max-product ({\tt maxprod})
\item AC variable elimination ({\tt acve})~\cite{chavira&darwiche07}
\end{itemize}
The last method compiles a BN or MN into an arithmetic circuit in which
exact inference is efficient. 

We also support the following learning methods:
\begin{itemize}
\item Chow-Liu algorithm ({\tt cl})~\cite{chow&liu68}
\item Dependency network learning ({\tt dnlearn})~\cite{heckerman&al00}
\item Learning BNs with local structure ({\tt aclearnstruct})~\cite{chickering&al97}
\item LearnAC ({\tt aclearnstruct})~\cite{lowd&domingos08}
\end{itemize}
LearnAC learns a BN with decision-tree CPDs using the
size of the corresponding AC as a learning bias.  This effectively
trades off accuracy and inference complexity.  It outputs both a BN
and an AC.  This is the most complex algorithm in the toolkit by far.

Finally, for models that are represented as arithmetic circuits, we
support:
\begin{itemize}
\item Exact inference ({\tt acquery})
\item Maximum likelihood parameter learning ({\tt acopt})
\end{itemize}

A few utility programs round out the toolkit:
\begin{itemize}
\item BN forward sampling ({\tt bnsample})
\item Likelihood or psuedo-likelihood model scoring ({\tt mscore})
\item Model conversion and conditioning on evidence ({\tt mconvert})
\item File info, for any supported file type ({\tt fstats})
\end{itemize}

Existing functionality is organized around the central theme of using
ACs for learning and inference, and comparing them to baseline BN
and MN methods.

\section{File Formats}

For data points, Libra uses comma-separated lists of variable values,
with asterisks representing values that are unknown.  This allows the
same format to be used for training examples and evidence
configurations.  Each data point is terminated by a newline.  In some
programs ({\tt mscore} and {\tt aclearn}), each data point may be
preceded by an optional weight, in order to learn or score a weighted
set of examples.  The default weight is 1.0.  The following are all
valid data points:
\begin{verbatim}
0,0,1,0,4,3,0
0.2|0,0,1,1,2,0,1
1000|0,0,0,0,0,0,0
\end{verbatim}

For arithmetic circuits, Libra uses a custom file format (.ac) that
lists the dimension of each variable in the first line of the file,
followed by the nodes in the network, one per line.  Each line
specifies the node type and any of its parameters, such as the value
of a constant node, the variable and value index for an indicator
variable node, and the indices of child nodes for sum and product
nodes.  Each node must appear before all of its parents. The root of
the circuit is therefore the last node.  After defining all nodes, an
arithmetic circuit file optionally describes how its parameters relate
to conjunctive features.

For Bayesian networks and dependency networks, Libra (mostly) supports
two previously defined file formats.  The first is the Bayesian
interchange format (BIF) for BNs and DNs with table 
CPDs.\footnote{Described here:
http://www.cs.cmu.edu/$\sim$fgcozman/Research/InterchangeFormat/Old/xmlbif02.html.}
Note that this is different from the newer XML-based XBIF format,
which may be supported in the future.\footnote{Scripts to translate between
BIF and XBIF are available here:\\
http://ssli.ee.washington.edu/$\sim$bilmes/uai06InferenceEvaluation/uai06-repository/scripts/.}

The second is the WinMine Toolkit XMOD format, which supports both
table and tree CPDs.\footnote{The WinMine Toolkit also provides a 
visualization tool for XMOD files, {\tt DNetBrowser.exe}.}  The advantage 
of tree CPDs over tables is that
they can easily express {\em context-specific} independencies, and
allow more compact CPDs for nodes with many parents.  Support for
tree CPDs is one key advantage of Libra over other BN toolkits.

For Markov networks, Libra defines a custom format.  The first line is
a comma-separated variable schema.  Following are the factor
definitions.  Different factor types (table, tree, feature set) have
different formats.  The simplest is a factor for a single features,
which is written out as a real-valued weight and a list of variable
conditions.  For example the following line defines a feature with a
weight of 1.2 for the conjunction $(X_0 = 1) \wedge (X_3 = 0) \wedge
(X_4 \neq 2)$:
\begin{verbatim}
1.2 +v0_1 +v3_0 -v4_2
\end{verbatim}

%\begin{align*}
%{\em t} &:= {\tt (v}{\em var}{\tt \_}{\em value} {\em t} {\em t}{\tt )} \\
%        &:= <float>
%\end{align*}

A feature set factor consists of a list of mutually exclusive features, each in
the format described above.  The list is surrounded is preceded by the word
``{\tt features}'' and an opening brace (`{\tt \{}'), and followed by a closing
brace (`{\tt \}}').  For example:
\begin{verbatim}
features {
-1.005034e-02 +v5_1 +v0_1
-2.302585e+00 +v5_0 +v0_1
-4.605170e+00 +v5_1 +v0_0
-1.053605e-01 +v5_0 +v0_0
}
\end{verbatim}

A table factor has the same format as a feature set, except with the word
``{\tt table}'' in place of the word ``{\tt features}'', and the features in
the list need not be mutually exclusive.  After reading a table factor, Libra
creates an internal tabular representation.  The size of this table is
exponential in the number of variables referenced by the listed features.

The format of a tree factor is similar to a LISP s-expression, as illustrated
in the following example:
\begin{verbatim}
tree {
(v1_0
    (v3_0
        (v0_0
            (v2_0 -1.905948e-02 -3.969694e+00)
            (v2_0 -5.320354e-02 -2.960105e+00))
        (v2_0 -2.341261e-01 -1.566675e+00))
    (v2_0 -2.121121e-01 -1.654822e+00))
}
\end{verbatim}
When $x_1 = 0$, $x_3 = 1$, and $x_2 = 1$, then the log value of this factor 
is {\tt -1.566675}.

To indicate an infinite weight, write ``{\tt inf}'' or {\tt -inf}''.

Libra also supports the Markov network model file format used the by
the UAI inference competition, described here:
{\tt http://www.cs.huji.ac.il/project/UAI10/fileFormat.php}.  However,
Libra does not currently support the UAI evidence or result file
formats.

% TODO: Come up with an example BN, represented as an AC,
% a BIF file, and an XMOD file.

\section{Using Libra}

The best introduction to installing Libra and using it to solve
problems is the Libra tutorial, which is available from the Libra home
page and included in the standard distribution.  In this section, we
provide more complete descriptions of the algorithms and their command
line options.

\subsection{Common Options}

Programs in Libra are designed to be run on the command line in a
UNIX-like environment or called by scripts in research or application
workflows.  No GUI environment is provided.  A list of options for any
command can be produced by running it with no arguments, or by
running it with a {\tt -help} or {\tt --help} argument.  We now
describe common options shared by many or all programs in the toolkit.

The output of the Libra programs is controlled by the following
options, available in every program:
\begin{itemize}
\item[] {\tt -log} {\em $<$file$>$}: Output logging information to the specified file
\item[] {\tt -v}: Enable verbose logging output.  Verbose output always
lists the full command line arguments, and often includes additional
timing information.
\item[] {\tt -debug}: Enable both verbose and debugging logging output.
Debugging output varies from program to program and is subject to
change.
\end{itemize}

Option names for the following common options are mostly standardized among 
the Libra programs that use them:
\begin{itemize}
\item[] {\tt -c} {\em $<$file$>$}: Arithmetic circuit
\item[] {\tt -i} {\em $<$file$>$}: Train or test data
\item[] {\tt -m} {\em $<$file$>$}: Model file, in MN, XMOD, BIF, or AC format
\item[] {\tt -o} {\em $<$file$>$}: Output model or data
\item[] {\tt -seed} {\em $<$int$>$}: Seed for the random number generator
\item[] {\tt -q} {\em $<$file$>$}: Query file
\item[] {\tt -ev} {\em $<$file$>$}: Query evidence file
\item[] {\tt -mo} {\em $<$file$>$}: File for writing marginals or MPE states
\item[] {\tt -sameev}: If specified, use the first line in the evidence
file as the evidence for all queries.
\end{itemize}

The last four options are exclusive to inference algorithms.  Each
inference algorithm prints out the conditional log probability of each
query given the evidence.  To output timing information as well, use
the verbose flag, {\tt -v}.


\subsection{Mean Field} 

Mean field ({\tt mf}) is an approximate inference algorithm that
attempts to minimize the reverse KL divergence between the specified
MN or BN (possibly conditioned on evidence) and a fully factored
distribution ({\em i.e.}, a product of single-variable marginals).
Libra's implementation updates one marginal at a time until all
marginals have converged, using a queue to keep track of which
marginals may need to be updated (see Algorithm 11.7
from~\cite{koller&friedman09}).  With the {\tt -roundrobin} flag,
Libra will instead update all marginals in parallel.  The stopping
criteria can be adjusted using the parameters {\tt -thresh}
(convergence threshold) or {\tt -maxiter} (maximum number of
iterations).  Rather than working directly with table or tree CPDs,
{\tt mf} converts both to a set of features and works directly with
the log-linear representation, ensuring that the compactness of tree
CPDs is fully exploited.

Our implementation is the first to support mean field inference
dependency networks, using the {\tt -depnet} option.  Since a
dependency network may not represent a consistent probability
distribution, the reverse KL divergence is undefined.  However, the
algorithm can be applied to dependency networks and tends to converge
in practice~\cite{lowd&shamaei11}.

\subsection{Loopy Belief Propagation}

Loopy belief propagation ({\tt bp}) is the application of an exact
inference algorithm for trees to general graphs that may have loops.
{\tt bp} is implemented on a factor graph, in which variables pass
messages to factors and factors pass messages back to variables in
each iteration.  All factor-to-variable or variable-to-factor messages
are passed in parallel, a message passing schedule known as
``flooding.''  For BNs, each factor is a CPD for one of the variables.
For factors represented as trees or sets of features, the running time
of a single message update is linear in the number of leaves or
features, respectively.  This allows {\tt bp} to run on networks with
factors that involve 100 or more variables, as long as the
representation is compact.

\subsection{Max-Product}

The max-product algorithm ({\tt maxprod}) is an approximate inference
algorithm to find the most probable explanation (MPE) state, the most
likely configuration of the non-evidence variables given the evidence.
Like {\tt bp}, max-product is an exact inference algorithm in a tree,
but may be incorrect in graphs with loops.  Max-product is implemented
identically to {\tt bp}, but replacing sum operations with max.

\subsection{Gibbs Sampling}

Gibbs sampling ({\tt gibbs}) is an instance of Markov-chain Monte
Carlo (MCMC) that generates samples by resampling a single variable at
a time conditioned on its Markov blanket.  The probability of any
query can be computed by counting the fraction of samples that satisfy
the query.  When evidence is specified, the values of the evidence
variables are fixed and never resampled.  By default, our
implementation computes the probabilities of conjunctive queries ({\em
e.g.}, $P(X_1 \wedge X_2 \wedge \neg X_4)$) or marginal queries ({\em
e.g.}, $P(X_1)$), optionally conditioned on evidence.  This is
potentially more powerful than MF and BP, which only compute marginal
probabilities.  To compute only marginal probabilities with Gibbs
sampling, use the {\tt -marg} option.  This is helpful when the specific
queries are very rare (such as long conjunctions) but can be well
approximated as the product of the individual marginal probabilities.

The running time of Gibbs sampling depends on the number of samples
taken.  Use {\tt -burnin} to set the number of burn-in iterations
(sampling steps thrown away before counting the samples); use {\tt
-sampling} to set the number of sampling iterations; and use {\tt
-chains} to set the number of repeated sampling runs.  For
convenience, these parameters can also be set using the {\tt -speed}
option which allows arguments of {\tt fast}, {\tt medium}, {\tt slow},
{\tt slower}, and {\tt slowest}, which range from 1000 to 10 million
total sampling iterations.  All speeds except for {\tt fast} use 10
chains and a number of burn-in iterations equal to 10\% of the
sampling iterations.  Samples can be output to a file using the {\tt
-so} option.

By default, Libra uses Rao-Blackwellization to make the probabilities
slightly more accurate.  This adds {\em fractional} counts to multiple
states by examining the distribution of the variable to be resampled.
For instance, suppose we wish to compute $P(X_3)$.  At some point,
while resampling $X_3$, we find that the probability of $X_3 =
\text{true}$ given its current Markov blanket is 0.001.  After
flipping a biased coin, we set $X_3$ to false.  In traditional Gibbs
sampling, we would add a count of 1 to the case where $X_3$ is false
and 0 to the case where $X_3$ is true.  In our Rao-Blackwellized
version, we add counts of 0.999 and 0.001, respectively.  This applies
both to computing conjunctive queries and marginals.  It can be
disabled with the flag {\tt -norb}.

Gibbs sampling can be run on a BN, MN, or dependency network.
Dependency networks must be in an accepted BN file format, and the
{\tt -depnet} flag must be used.

\subsection{AC Variable Elimination}

AC variable elimination ({\tt acve})~\cite{chavira&darwiche07}
compiles a BN or MN by simulating variable elimination and encoding
the addition and multiplication operations into an AC.  ACVE
represents the original and intermediate factors as algebraic decision
diagrams (ADDs) with AC nodes at the leaves.  As each variable is
summed out, the leaves of the ADDs are replaced with new sum and
product nodes.  By producing an AC, ACVE can answer many queries
simultaneously.  By using ADDs, ACVE can exploit context-specific
independence much better than previous methods based on variable
elimination.  See Chavira and Darwiche~\cite{chavira&darwiche07} for
details.

The one difference between our implementation and the standard
algorithm is that we extend our ADDs to allow $k$-way splits for
variables with $k$ values.  In the standard algorithm, $k$-valued
variables are converted into $k$ Boolean variables, along with
constraints to ensure that exactly one of these variables is true at a
time.  We also omit the circuit node cache, which we find has little
effect on circuit size at the cost of significantly slowing
compilation.

\subsection{Chow-Liu Algorithm}

The Chow-Liu algorithm ({\bf cl})~\cite{chow&liu68} learns the maximum
likelihood tree-structured BN from data.  The algorithm works by first
computing the mutual information between each pair of variables and
then greedily adding the edge with highest mutual information
(excluding edges that would form cycles) until a spanning tree is
formed.  (For sparse data, faster implementations are
possible~\cite{meila99}.)

\subsection{AC Structure Learning}

LearnAC ({\tt aclearnstruct})~\cite{lowd&domingos08} learns a BN with
decision-tree CPDs using the size of the corresponding AC as a
learning bias.  This effectively trades off accuracy and inference
complexity.  It outputs both a BN and an AC.  This is the most complex
algorithm in the toolkit by far.

To learn a BN without learning an AC, use the {\tt -noac} flag.  This
performs the exact same structure search as before, but without
constructing an AC, and with no penalty based on inference complexity.
This is useful for obtaining a baseline BN.  

% With the {\tt -depnet}
% flag, the acyclicity constraint is also ignored, leading to a set of
% conditional distributions known as a {\em dependency
% network}~\cite{heckerman&al00}.

An allowed parents file may be specified ({\tt -parents} {\em $<$file$>$}),
which restricts the sets of parents structure learning is allowed to choose for
each variable.  Restrictions can limit the parents to a specific set of parents
(``{\tt none except 1 2 8 10}'') or to any parent not in a list (``{\tt all
except 3 5}'').  An example parent file is below: 
\begin{verbatim}
# This is a comment
0: all except 1 3   # only vars 1 and 3 may be parents of 0
1: none except 5 2  # var 1 may only have var 5 or 2 as a parent
2: none             # var 2 may have no parents
5: all              # var 5 may have any parents
\end{verbatim}

\subsection{DN Structure Learning}

A dependency network (DN) specifies a conditional probability
distribution (CPD) for each variable given its
parents~\cite{heckerman&al00}.  However, unlike a Bayesian network,
the graph of parent-child relationships may contain cycles.  As a
result, DNs do not always represent consistent probability
distributions, making their semantics somewhat problematic.  However,
they can still be learned from data and queried using Gibbs sampling
or the mean field inference algorithm~\cite{lowd&shamaei11}.

Dependency networks with tree-structured conditional probabiity
distributions can be learned with {\tt dnlearn}.  The algorithm used
is similar to that of Heckerman et al.~\cite{heckerman&al00}.  As with
{\tt aclearnstruct}, the user can set the prior counts on the
multinomial leaf distributions ({\tt -prior}) as well as a per-split
penalty ({\tt -ps}) to prevent overfitting.  The {\tt -kappa} option
is equivalent to a setting a per-split penalty of log kappa.

\subsection{AC Parameter Learning}

AC parameters can be learned or otherwise optimized using {\tt acopt}.
The input circuit is specified with {\tt -c}.

Given training data ({\tt -i} {\em $<$file$>$}), {\tt acopt} finds
parameters that maximize the log-likelihood of the training data.
This works for any AC that represents a log linear model, including
BNs and Markov networks.  Our implementation uses
L-BFGS~\cite{liu&nocedal89}, a standard convex optimization method.
The gradient of the log-likelihood is computed in each iteration by
differentiating the circuit, which is linear in circuit size.  Since
this is a convex problem, the parameters will eventually converge to
their optimal values.  The maximum number of iterations can be
specified using {\tt -maxiter}.

Given a BN or MN ({\tt -m}) and, optionally, evidence ({\tt -ev}),
{\tt acopt} supports two other kinds of parameter optimization.
Neither is yet described in the literature.

The first is to minimize the reverse KL divergence between the source
network (optionally conditioned on evidence) and the AC ({\em i.e.},
$D_{\text{KL}}(\text{AC}||\text{BN})$).  This is similar to mean
field, except that an AC is used in place of a fully factored
distribution, and the optimization is performed using L-BFGS instead
of message passing.

The second type of optimization ({\tt -gibbs}) approximately minimizes
the regular KL divergence, $D_{\text{KL}}(\text{BN}||\text{AC})$ or
$D_{\text{KL}}(\text{MN}||\text{AC})$, by generating samples from the
BN or MN (optionally conditioned on evidence) and selecting AC
parameters to maximize their likelihood.  Samples are generated using
Gibbs sampling, with parameters analogous to those in the {\tt gibbs}
program.  The most important options are {\tt -gspeed} or {\tt
-gc}/{\tt -gb}/{\tt -gs} to set the number of samples.  Increasing the
number of samples yields a better approximation but takes longer to
run.  This is similar to running {\tt gibbs}, saving the samples using
{\tt -so}, and then running {\tt acopt} with {\tt -i}, as described
above.  However, {\tt acopt -gibbs} is faster since it only needs to
compute the sufficient statistics instead of storing and reloading the
entire set of samples.

The main application of {\tt acopt} is for for performing approximate
inference using ACs, as described by~\cite{lowd&domingos10}.  The key
idea of~\cite{lowd&domingos10} is to generate samples from a Bayesian
network ({\tt bnsample}), learn an AC from the samples ({\tt
aclearn}), and then optimize the AC's parameters for specific evidence
({\tt acopt}).

\subsection{Exact AC Inference}

Exact inference in ACs is done through {\tt acquery}, which accepts
similar arguments to the approximate inference algorithms. See
Darwiche~\cite{darwiche03} for a thorough description of ACs and how
to use them for inference.  We provide a brief description of the
methods below.

To compute the probability of a conjunctive query, we set all
indicator variables in the AC to zero if they are inconsistent with
the query and to one if they are consistent.  For instance, to compute
$P(X_1 = \text{true} \wedge X_3 = \text{false})$, we would set the
indicator variables for $X_1=\text{false}$ and $X_3=\text{true}$ to
zero and all others to one.  Evaluating the root of the circuit gives
the probability of the input query.  Conditional probabilities are
answered by taking the ratio of two unconditioned probabilities:
\[
P(Q|E) = \frac{P(Q \wedge E)}{P(E)}
\]
where $Q$ and $E$ are conjunctions of query and evidence variables,
respectively.  Both $P(Q \wedge E)$ and $P(E)$ can be computed using
previously discussed methods.  Evaluating the circuit is linear in the
size of the circuit.

We can also differentiate the circuit to compute all marginals in
parallel ({\tt -marg}), optionally conditioned on evidence.
Differentiating the circuit consists of an upward pass and a downward
pass, each of which is linear in the size of the circuit.  See
Darwiche~\cite{darwiche03} for more details.

Finally, we can compute the most probable explanation (MPE) state
({\tt -mpe}), which is the most likely configuration of the
non-evidence variables given the evidence.  When {\tt -mpe} is used
without a query file, it prints out the MPE state for each evidence.
When a query file is specified, it prints out the fraction of
non-evidence variables that are different between the query state and
the inferred MPE state.  When the MPE state is not unique, {\tt
acquery} selects one of the MPE states arbitrarily.


\subsection{Utilities}

The program {\tt mscore} computes the log-likelihood of a set of
examples for BNs or ACs.  For MNs, {\tt mscore} can be used to compute
the unnormalized log-likelihood, which will differ from the true
log-likelihood by {\tt log Z}, the log partition function of the MN.
Using the {\tt -pll} flag, {\tt mscore} will compute the
pseudo-log-likelihood of a set of examples for BNs, MNs, or DNs.
Pseudo-log-likelihood is not currently supported for ACs.

The program {\tt bnsample} can be used to generate a set of
independent samples from a BN using forward sampling.  Each variable
is sampled given its parents, in topological order.  Use {\tt -n} to
indicate the number of samples and {\tt -seed} to choose a random
seed.

The program {\tt mconvert} performs conversions among the AC, BN, and
MN file formats, and conditions models on evidence ({\tt -ev}).  ACs
can be converted to ACs or MNs; BNs can be converted to BNs or MNs;
and MNs can be converted to MNs.  If an evidence file is specified
(using {\tt -ev}), then the output model must be an AC or MN.  If the
{\tt -feat} option is specified when outputting an MN, then each
factor in the MN will be a set of features.

{\tt fstats} gives basic information for files of most types supported
by Libra.

% TODO -- what other sections should I add?  Something about
% contributing to Libra?  Future plans?

\newpage

\bibliographystyle{plain}
\bibliography{libra}

\end{document}
